package com.feishi.core.util.common.lecode.tree;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: caixq
 * Date: 2020-08-20
 * Time: 上午11:15
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {

        if(p==null&&q==null)return true;
        if(p==null||q==null||p.val!=q.val){
            return false;
        }

        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    /**
     * 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
     *
     * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
     *
     * "123"
     * "132"
     * "213"
     * "231"
     * "312"
     * "321"
     * 给定 n 和 k，返回第 k 个排列。
     * */
    public static String getPermutation(int n, int k) {
        int[] ints=new int[n];
        for (int i = 0; i < n; i++) {
            ints[i]=i;
        }
        int i=1;
        int v=1;
        while (v<k){
            v*=++i;
        }
        v=v/i;
        i--;
        while (k>0){
            int step=(k-1)%v+1;
            int index=i;
            int t=ints.length-1+index-step-1;
            int tmp=ints[t];
            for (int j = t; j >= ints.length-index-1; j--) {
                ints[j]=ints[j-1];
            }
            ints[t]=tmp;
            System.out.println(step+","+index);
            k/=i;
            v=v/i--;
        }

        return Arrays.toString(ints);
    }
    public static String minWindow(String s, String t) {
        Map<Character,Integer> sMap=new HashMap<>();
        Map<Character,Integer> tMap=new HashMap<>();
        for (Character character : t.toCharArray()) {
            tMap.put(character,tMap.getOrDefault(character,0)+1);
        }
        int a=0;
        int b=t.length();
        for (int i = a; i < b; i++) {
            sMap.put(s.charAt(i),sMap.getOrDefault(s.charAt(i),0)+1);
        }
        int start=a,end=b;
        while (b<s.length()){

        }



        return s.substring(a,b);
    }
    /**
     * @param k: An integer
     * @param n: An integer
     * @return: An integer denote the count of digit k in 1..n
     */
    public static int digitCounts(int k, int n) {
        int count=0,singlecount=0;
        int p=n;
        if(k==0) {
            while (p!=0){
                p=p/10;
                singlecount+=p;
            }
            return singlecount+1;
        };
        if(n==0) return 0;
        int t=1;//表示处理数字的位数 num=0表示处理个位 1表示十位等
        while(p!=0){
            if((p%10)>k)    singlecount=((p/10+1)*t);
            if((p%10)==k)   singlecount=((p/10)*t+(n%t)+1);
            if((p%10)<k)    singlecount=((p/10)*t);
            count+=singlecount;
            p=p/10;
            t*=10;
        }
        return count;
    }

    /**
     * @param n: An integer
     * @return: return a  integer as description.
     */
    public static int nthUglyNumber(int n) {
        // write your code here

        int index=1;
        int[] nums=new int[n];
        int p2,p3,p5;
        p2=p3=p5=0;
        nums[0]=1;
        int v2,v3,v5;
        for (int i = 1; i < n; i++) {
            v2=nums[p2]*2;
            v3=nums[p3]*3;
            v5=nums[p5]*5;
            nums[i]=min(v2,v3,v5);
            if(nums[i]==v2)p2++;
            if(nums[i]==v3)p3++;
            if(nums[i]==v5)p5++;
        }

        return nums[n-1];
    }

    private static int min(int ...is) {
        int min=is[0];
        for (int i = 1; i < is.length; i++) {
            min=min<is[i]?min:is[i];
        }
        return min;
    }
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        // write your code here
        for (int i = 0; i < n; i++) {

        }

        return nums[n-1];
    }

    private void switchIndex(int[] nums, int i, int j) {
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    /**
     * 给定一个二叉树，检查它是否是镜像对称的。
     * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
     * */
    public boolean isSymmetric(TreeNode root) {

        return check(root.left,root.right);
    }

    private boolean check(TreeNode left, TreeNode right) {
        if(left==null&&right==null)return true;
        if(left==null||right==null)return false;
        return left.val==right.val&&check(left.left,right.right)&&check(left.right,right.left);
    }
    /**
     * 根据一棵树的前序遍历与中序遍历构造二叉树。
     * 注意:
     * 你可以假设树中没有重复的元素。
     * */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0||inorder.length==0){
            return null;
        }
        TreeNode root=new TreeNode (preorder[0]);
        for(int i=0;i<preorder.length;i++){
            if(preorder[0]==inorder[i]){
                root.left=buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));
                root.right=buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length),Arrays.copyOfRange(inorder,i+1,inorder.length));
                break;
            }
        }
        return root;
    }
    /**
     * 给定一个二叉树，找出其最大深度。
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * */
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> results = new ArrayList<>();

        // add the root element with a delimiter to kick off the BFS loop
        LinkedList<TreeNode> node_queue = new LinkedList<>();
        node_queue.addLast(root);
        node_queue.addLast(null);

        LinkedList<Integer> level_list = new LinkedList<>();
        boolean is_order_left = true;

        while (node_queue.size() > 0) {
            TreeNode curr_node = node_queue.pollFirst();
            if (curr_node != null) {
                if (is_order_left)
                    level_list.addLast(curr_node.val);
                else
                    level_list.addFirst(curr_node.val);

                if (curr_node.left != null)
                    node_queue.addLast(curr_node.left);
                if (curr_node.right != null)
                    node_queue.addLast(curr_node.right);

            } else {
                // we finish the scan of one level
                results.add(level_list);
                level_list = new LinkedList<>();
                // prepare for the next level
                if (node_queue.size() > 0)
                    node_queue.addLast(null);
                is_order_left = !is_order_left;
            }
        }
        return results;
    }
    /**
     * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
     * */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root==null)return new ArrayList<>();
        List<TreeNode> nodes=new ArrayList<>();
        List<List<Integer>> result=new ArrayList<>();
        nodes.add(root);
        while (true){
            result.add(nodes.stream().map(node->node.val).collect(Collectors.toList()));
            List<TreeNode> nodeList=new ArrayList<>();
            for (TreeNode node : nodes) {
                if(node.left!=null)nodeList.add(node.left);
                if(node.right!=null)nodeList.add(node.right);
            }
            nodes=nodeList;
            if (nodes.size()==0)break;
        }
        return result;
    }
    /**
     * 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
     *
     * 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
     *
     * 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
     * */
    public static int maxProfit(int[] prices) {
//        if(prices.length<2)return 0;
//        int out=0;
//        int status=0;
//        List<Integer[]> all=new ArrayList<>();
//        Integer[] index=null;
//        for (int i = 0; i <prices.length-1; i++) {
//            if(prices[i]<prices[i+1]){
//                if(status==0){
//                    index=new Integer[]{i,0};
//                    status=1;
//                }
//            }else {
//
//                if(status==1){
//                    index[1]=i;
//                    all.add(index);
//                    index=null;
//                    status=0;
//                }
//
//            }
//        }
//        if(index!=null){
//
//            index[1]=prices.length-1;
//            all.add(index);
//        }
//        int i = 0;
//        for (; i < all.size()-1; i++) {
//            out+=prices[all.get(i)[1]]-prices[all.get(i)[0]];
//            if(all.get(i+1)[0]-all.get(i)[1]>1){
//                continue;
//            }
//            int a=prices[all.get(i)[1]]-prices[all.get(i)[1]-1];
//            int b=prices[all.get(i)[1]]-prices[all.get(i)[1]+1];
//            int c=prices[all.get(i)[1]+2]-prices[all.get(i)[1]+1];
//            int d=prices[all.get(i+1)[1]]-prices[all.get(i+1)[0]];
//            int min=Math.min(Math.min(a,b),c);
//
//            if(prices[all.get(i)[1]+2]-prices[all.get(i)[1]]>0){
//
//            }
//            if(d==min){
//                i++;
//                continue;
//            }
//            if(min==b){
//                out-=b;
//            }else if(min==a){
//                if(c==d){i++;continue;}
//                out-=a;
//            }else if(min==c){
//                out-=c;
//            }
////            System.out.println(Arrays.toString(all.get(i)));
//        }
//        if(all.size()>0&&i== all.size()-1)
//        out+=prices[all.get(all.size()-1)[1]]-prices[all.get(all.size()-1)[0]];
//
//        return out;
        if (prices.length <2) {
            return 0;
        }
//        int n = prices.length;
//        int[][] f =new int[prices.length][3];
//        f[0][0]=-prices[0];
//        f[0][1]=0;
//        f[0][2]=0;
//        for (int i = 1; i < prices.length; i++) {
//            f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
//            f[i][1] = f[i - 1][0] + prices[i];
//            f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
//        }
//        for (int[] ints : f) {
//            System.out.print(ints[0]+"\t");;
//        }
//        System.out.println();
//        for (int[] ints : f) {
//            System.out.print(ints[1]+"\t");;
//        }
//        System.out.println();
//        for (int[] ints : f) {
//            System.out.print(ints[2]+"\t");;
//        }
//        System.out.println();
//
//         return Math.max(f[n - 1][1], f[n - 1][2]);
        int a=-prices[0],a1,b=0,b1,c=0,c1;
        for (int i = 1; i < prices.length; i++) {
            a1=Math.max(a,c-prices[i]);
            b1=a+prices[i];
            c1=Math.max(b,c);
            a=a1;b=b1;c=c1;
        }
        return Math.max(b,c);
    }
    /**
     * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
     * */
    public static String removeDuplicateLetters(String s) {

        int[] cnt = new int[26];
        int pos = 0;
        for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) pos = i;
            if (--cnt[s.charAt(i) - 'a'] == 0) break;
        }
        System.out.println(s.length()>0?s.charAt(pos):"-");
        String out=s.length() == 0 ? "" : (s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), "")));

        return out;
    }
    /**
     * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
     * */
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }
        Arrays.sort(coins);
        List<Integer>[] lists=new List[coins.length];
        for (int i = 0; i < lists.length; i++) {
            lists[i]=new ArrayList<>();
        }
        

        return amount;
    }
    public static void main(String[] args) {
        System.out.println(removeDuplicateLetters("reabcsdccabra"));;
    }
}
